package class08


/*
	给定一个正数 N， 表示你在纸上写下 1 ~ N 所有的数字
	返回在书写过程种，一共写下了多少个1

	方案一：
		1. 遍历 1 ~ N，计算N中包含1的数量

	方案二：
		O(log10N * log10N)
		13625     1 ~ 13625 过程中有几个1
		从 1 ~ i 的过程中有写了几个1给我返回。
		f(13625) int {
			// 1. 非递归
				求 3626 ~ 13625 中有几个1
				最高位是1：
					1. 万位一的个数：
						N % 10^k-1  k 表示位数
					2. 千位一个个数：
						个位，十位，百位固定的情况下，
						万位有且仅有一个选择
						所以共有 10^3 个
					3. 百位与千位同理 10^3
					4. 十位一样也是 10^3
					5. 个位一样也是 10^3
					6. 表达式为 N % 10^k-1 + (10^k-2)*(k-1)
				最高位不是1：
					626~3625
					1. 高位一的个数：
						10^k-1 个1
					2. 对区间分段
						1）626 ~ 1625
						2) 1626 ~ 2625
						3) 2626 ~ 3625
						非高位，此时除了高位，其他位固定时，
						每个区间都有一个数与之匹配，所以
						1的个数为：最高位*10^k-2*(k-1)
			// 2.
				+ f(3625)
		}

		f(3625) int {
			// 1. 非递归
				求 626 ~ 3625 中有几个1
			// 2.
				+ f(625)
		}



*/


// 方案一：
func getOneNums1(N int) int {
	if N < 1 {
		return 0
	}
	var count int
	for i:=1; i<=N; i++ {
		count += GetOneCountByNum(i)
	}
	return count
}

func GetOneCountByNum(num int) int {
	// 1001  -- 2
	var ans int
	for num != 0 {
		if num % 10 == 1 {
			ans++
		}
		num /= 10
	}
	return ans
}

// 方案二：
func getOneNums2(N int) int {
	if N <= 0 {
		return 0
	}
	l := getNumLen(N)
	if l == 1 {
		return 1
	}
	tmp1 := powerBaseOf10(l-1)

	firstOne := N/tmp1

	var firstNum, secondNum int
	if firstOne == 1 {
		firstNum = N%tmp1 + 1
	} else {
		firstNum = tmp1
	}
	secondNum = firstOne * powerBaseOf10(l-2) * (l-1)

	return firstNum + secondNum + getOneNums2(N%tmp1)
}

func getNumLen(n int) int {
	var res int
	for n > 0 {
		res++
		n /= 10
	}
	return res
}

func powerBaseOf10(k int) int {
	var res int = 1
	for k != 0 {
		res *= 10
		k--
	}
	return res
}
